package class3;

import common.ListNode;
import common.ListNodeUtils;

import java.util.HashMap;
import java.util.Map;

/**
 * https://leetcode.cn/problems/fu-za-lian-biao-de-fu-zhi-lcof/description/
 * 复制含有随即指针节点的链表
 * <p>
 * 解题思路：
 * 1.通过map，复制节点
 * 2.获取节点key，进行连接
 */
public class Code18_CopyRandLinked {
    public static void main(String[] args) {
        ListNode head = ListNodeUtils.getLinked(1, 2, 3, 4);
        head.rand = head.next.next;
        head.next.rand = head;
        head.next.next.next.rand = head.next;
        ListNodeUtils.print(head);
        ListNode listNode = copyRandLink(head);
        ListNodeUtils.print(listNode);
        ListNode listNode1 = copyRandLink2(head);
        ListNodeUtils.print(listNode1);

    }

    public static ListNode copyRandLink(ListNode head) {
        Map<ListNode, ListNode> map = new HashMap<>();
        ListNode cur = head;
        // 先将旧的链表存入map中
        while (cur != null) {
            // k为当前节点，val为当前节点的复制节点
            map.put(cur, new ListNode(cur.val));
            cur = cur.next;
        }
        cur = head;
        while (cur != null) {
            // 获取当前节点的复制节点，复制节点的 next 值为
            // 1 - 2 - 3 -> 1' - 2' - 3'
            // get(1) = 1',然后1'的next实际是get(2),也就是get(cur.next)
            map.get(cur).next = map.get(cur.next);

            // cur.rand 也是 key，通过get(cur.rand)可以获取到对应节点的复制节点 rand = 2 则获取 2'
            map.get(cur).rand = map.get(cur.rand);
            cur = cur.next;
        }
        return head;
    }

    public static ListNode copyRandLink2(ListNode head) {
        if (head == null) return null;
        ListNode cur = head;
        ListNode next;
        /**
         * 先复制一遍各个子节点
         */
        while (cur != null) {
            next = cur.next; // 实际的次节点
            cur.next = new ListNode(cur.val);
            cur.next.next = next;
            cur = next;
        }
        cur = head;
        ListNode curCop;
        while (cur != null) {
            next = cur.next.next;
            curCop = cur.next;
            // 注意，这里 curCop.rand.next 就是复制节点
            // 因为链表结构是： 1   1   2   2   3   3   4   4
            curCop.rand = curCop.rand != null ? curCop.rand.next : null;
            cur = next;
        }

        ListNode res = head.next;
        cur = head;
        while (cur != null) {
            next = cur.next.next;
            curCop = cur.next;
            cur.next = next;
            curCop.next = next != null?next.next:null;
            cur = next;
        }
        return res;
    }
}
